package linkList;

import linkList.IntersectionNode.ListNode;

public class IntersectionNode {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    // 法一：若有重合，那么最终剩余的数量一定是相同的，因此先调整指长度相同
    // 注意：判断相同节点不应该比较val，而是直接比较节点，看是否指向同一地址
    // o（m+n） o1
    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        // 求长度
        int lengthA = 0, lengthB = 0;
        ListNode start = headA;
        while (start != null) {
            lengthA++;
            start = start.next;
        }
        
        start = headB;
        while (start != null) {
            lengthB++;
            start = start.next;
        }
        if (lengthA > lengthB) {
            int count = lengthA - lengthB;
            while (count > 0) {
                headA = headA.next;
                count--;
            }
            lengthA=lengthB;
        } else if (lengthB > lengthA) {
            int count = lengthB - lengthA;
            while (count > 0) {
                headB = headB.next;
                count--;
            }
            lengthB=lengthA;

        }
        // 可能重合也可能不重合
        while (lengthA>0) {
            if (headA.val==headB.val) {
                return headA;
            }
            headA=headA.next;
            headB=headB.next;
        }
        // 可能没有重合
        return null;
    }
    // 法二：使用hashset，然后containsKey
    // 根据整数列表创建链表
    public static ListNode createLinkedList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }
        
        // 创建头节点
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        
        // 依次创建后续节点
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        
        return head;
    }
    public static void main(String[] args) {
        int[] arrA = {4, 1, 8, 4, 5};
        ListNode headA = createLinkedList(arrA);
        
        // 创建 listB = [5,6,1,8,4,5] 对应的链表
        int[] arrB = {5, 6, 1, 8, 4, 5};
        ListNode headB = createLinkedList(arrB);
        ListNode intersectionNode1 = getIntersectionNode1(headA, headB);
        System.out.println(intersectionNode1.val);
    }
}
